package main.java.LeetCode.ClassicalAlgorithm.Sort.Impl;


import main.java.LeetCode.ClassicalAlgorithm.Sort.Sort;
import main.java.LeetCode.CommonSolution.ListNode;

@SuppressWarnings("ALL")
public class QuickSort implements Sort {
    private final String NAME = "QuickSort";
    @Override
    public void sort(int[] arr) {
        doSort(arr,0,arr.length-1);
        System.out.print(NAME+": ");
        for(int num:arr){
            System.out.print(num+" ");
        }
        System.out.println();
    }

    private void doSort(int[] arr,int start,int end){
        if(start>=end)
            return;
        int flag = arr[start];
        int left = start+1;
        int right = end;
        while (left<right){
            while (right>left&&arr[right]>=flag){
                right--;
            }
            while (right>left&&arr[left]<=flag){
                left++;
            }
            swap(arr,left,right);
        }
        if(arr[left]<flag)
            swap(arr,start,left);
        doSort(arr,start,left-1);
        doSort(arr,left,end);
    }
    private void swap(int[] arr,int start,int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }

    public void sortList(ListNode head){
        doSortForList(head,null);
        while (head!=null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }

    private void doSortForList(ListNode left,ListNode right){
        if(left == right)
            return;

        ListNode tempL = left.next;
        ListNode tempNode = left;
        int tempVal;

        while (tempL!=right){
            if(tempL.val<left.val){
                tempVal = tempL.val;
                tempL.val = tempNode.next.val;
                tempNode.next.val = tempVal;
                tempNode = tempNode.next;
            }
            tempL = tempL.next;
        }

        tempVal = tempNode.val;
        tempNode.val = left.val;
        left.val = tempVal;

        doSortForList(left,tempNode);
        doSortForList(tempNode.next,right);
    }

}
